package com.str.graphs;
public class Dijkstra {
  private static void printout(Graph g, int s, int[] d) {
    for (int i=0; i<g.n(); i++)
      System.out.println(s + " -> " + i + " (" + d[i] + ")");
  }
  
  private static int minVertex(Graph g, int[] d, boolean[] visited) { // Find min cost vertex
    int v = 0;
    for (int i=0; i<g.n(); i++)    // Set v to an unvisited vertex
      if (!visited[i]) { v = i; break; }
    for (int i=v+1; i<g.n(); i++)    // Now find smallest D value
      if ((!visited[i]) && (d[i] < d[v])) v = i;
    return v;
  }

  public static void dijkstra(Graph g, int s) {  // Compute shortest path distances
    boolean[] visited = new boolean[g.n()];
    int[] d = new int[g.n()];
    for (int i=0; i<g.n(); i++) {   // Initialize
      visited[i] = false;
      d[i] = Integer.MAX_VALUE;
    }
    d[s] = 0;
    for (int i=0; i<g.n(); i++) {       // Process the vertices
      int v = minVertex(g, d, visited);
      visited[v] = true;      
      if (d[v] == Integer.MAX_VALUE) return; // Remaining vertices unreachable
      for (int w = g.first(v); w < g.n(); w = g.next(v,w))
        if (d[w] > (d[v] + g.weight(v,w)))
	      d[w] = d[v] + g.weight(v,w);
    }
    printout(g, s, d);
  }
}
